package com.congee02.graph;

import java.util.*;

public class GraphLoopDFS {

    public boolean hasCycle(int num, int[][] edges) {

        boolean[] visited = new boolean[num];
        boolean[] onStack = new boolean[num];

        List<Integer>[] adjacency = new List[num];

        for (int[] edge : edges) {

            int from = edge[0];
            int to = edge[1];

            if (adjacency[from] == null) {
                adjacency[from] = new ArrayList<>();
            }

            adjacency[from].add(to);

        }

        for (int i = 0 ; i < num ; i ++ ) {

            if (visited[i]) {
                continue;
            }
            if (dfsHelp(i, visited, onStack, adjacency)) {
                return true;
            }

        }

        return false;
    }

    private boolean dfsHelp(int cur, boolean[] visited, boolean[] onStack, List<Integer>[] adjacency) {
        visited[cur] = true;
        onStack[cur] = true;

        if (adjacency[cur] == null) {
            onStack[cur] = false;
            return false;
        }

        for (Integer neighbor : adjacency[cur]) {

            if (! visited[neighbor]) {
                if (dfsHelp(neighbor, visited, onStack, adjacency)) {
                    return true;
                }
            } else if (onStack[neighbor]) {
                return true;
            }

        }

        onStack[cur] = false;
        return false;
    }


}
